#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> length;
        for (int i = 0; i < nums.size(); i++)
        {
            if (length.size() == 0 || nums[i] > length.back())
            {
                length.push_back(nums[i]);
            }
            else
            {
                int left = 0;
                int right = length.size() - 1;
                int mid = (left + right) / 2;
                while (left < right)
                {
                    if (length[mid] < nums[i])
                    {
                        left = mid + 1;
                        mid = (left + right) / 2;
                    }
                    else
                    {
                        right = mid;
                        mid = (left + right) / 2;
                    }
                }
                length[right] = nums[i];
            }
        }
        return length.size();
    }
};


class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int i = 0;
        int ret = 0;
        int j;
        for (j = 1; j < nums.size(); j++)
        {
            if (nums[j] <= nums[j - 1])
            {
                ret = max(ret, j - i);
                i = j;
            }

        }
        ret = max(ret, j - i);
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prevmin = prices[0];
        int  ret = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            ret = max(ret, prices[i] - prevmin);
            if (prices[i] < prevmin)
                prevmin = prices[i];
        }
        return ret;
    }
};
int main()
{
    vector<int> nums = { 10,9,2,5,3,7,101,18 };
    Solution().lengthOfLIS(nums);
    return 0;
}